import rubik
from collections import deque

# Stores properties of the node - layer number and move that lead from parent 
class NodeProperties:
    def __init__(self, parent_move, d):
        self.parent_move = parent_move # move that lead to this node
        self.d = d

def shortest_path(start, end):
    """
    Using 2-way BFS, finds the shortest path from start_position to
    end_position. Returns a list of moves. 

    You can use the rubik.quarter_twists move set.
    Each move can be applied using rubik.perm_apply
    """
    if start == end:
        return []
    
    nodeProps1 = {start : NodeProperties(None, 0)} # node-to-properties mapping for the bfs1
    nodeProps2 = {end : NodeProperties(None, 0)}  # node-to-properties mapping for the bfs2
    
    parent1 = {start : None} # parent relation for the bfs1
    parent2 = {end : None} # parent relation for the bfs2
    
    deque1 = deque() # deque for the bfs1
    deque2 = deque() # deque for the bfs2
    
    deque1.append(start)
    deque2.append(end)
    
    result = [] # if is None - no solution
    
    while True:
        n1 = deque1.popleft()
        n2 = deque2.popleft()
        
        if is_handshake(n1, parent1, parent2):
            append_moves(result, parent1, nodeProps1, n1, False)
            append_moves(result, parent2, nodeProps2, n1, True)
            break
        elif is_handshake(n2, parent1, parent2):
            append_moves(result, parent1, nodeProps1, n2, False)
            append_moves(result, parent2, nodeProps2, n2, True)
            break
        elif check_no_solution(n1, nodeProps1) or check_no_solution(n2, nodeProps2) :
            result = None
            break
        else:
            for q in rubik.quarter_twists:
                apply_and_enque(q, n1, parent1, nodeProps1, deque1)
                apply_and_enque(q, n2, parent2, nodeProps2, deque2)

    return result

def is_handshake(n, parent1, parent2):
    return n in parent1 and n in parent2

# search gone further than half the diameter
def check_no_solution(n, nodeProps):
    return nodeProps[n].d > 7

# used to reconstruct path in the graph of the game states
def append_moves(result, parent, nodeProps, n, isReverse):
    result_temp = []
    while n in parent and not parent[n] is None:
        move = nodeProps[n].parent_move
        if isReverse:
            move = rubik.perm_inverse(move)
        result_temp.append(move)
        n = parent[n]
        
    if not isReverse:
        result_temp.reverse()
        
    result.extend(result_temp)

# exlore nodes and add them to bfs deque
def apply_and_enque(q, n, parent, nodeProps, deque):
    n2 = rubik.perm_apply(q, n) # new position
    if n2 not in parent:
        parent[n2] = n
        parentProps = nodeProps[n] 
        nodeProps[n2] = NodeProperties(q, parentProps.d + 1)
        deque.append(n2)